'''
@Descripttion: 
@version: 
@encoding: utf-8
@Author: qiurongcan
Date: 2025-10-10 15:52:26
LastEditTime: 2025-10-10 16:28:49
'''
from collections import defaultdict

class Solution:
    def pathSum(self, root, targetSum):
        ans = 0
        cnt = defaultdict(int)
        cnt[0] = 1

        def dfs(node, s):
            if not node:
                return
            
            nonlocal ans
            s += node.val
            # 当作路径终点，看看有几个起点
            ans += cnt[s - targetSum] # 10 - 8 = 2, 查找前缀和为2的个数
            cnt[s] += 1 # 此个前缀 + 1
            dfs(node.left, s)
            dfs(node.right, s)
            cnt[s] -= 1

        dfs(root, 0)
        return ans
        



